/*
 * The concrete SearchEngine using Transposition Table and History Heuristic
 * This engine using for level TopPlayer and WorldClass
 */

#ifndef _DSQTTHHENGINE_H
#define _DSQTTHHENGINE_H

#include "CDSQBaseInfo.h"
#include "CAlgSearchEngine.h"

enum EntryType { EntryTypeExact = 0, EntryTypeLowerBound, EntryTypeUpperBound };

typedef struct _HashItem
{
	EntryType entry_type;
	long long checksum;
	short depth;
	short eval;
} HashItem, *pHashItem;

class CDSQTTHHEngine : public CAlgSearchEngine
{
	typedef CAlgSearchEngine PARENT;

public:
	virtual void backToInitialState();

protected:
	virtual void RunSearchEngine(CDSQBoard* pBoard, AKSideIndex side);
	int TTHHAlphaBeta(CDSQBoard* pBoard, unsigned int depth, int alpha, int beta, AKSideIndex side);

private:
	/**********HistoryHeuristic Engine*********/
	/*Sort the current moves*/
	void MergeSort(PieceMove* source, int n,int direction);
	/*Add the best move to the History*/
	void EnterHistoryScore(PieceMove *move,int depth);
	/*Get the score of the move*/
	int GetHistoryScore(PieceMove *move);
	/*Clear the HistoryTable*/
	void ResetHistoryTable();
	
	void Merge_A(PieceMove* source,PieceMove* target,int l,int m, int r);
	void MergePass(PieceMove* source, PieceMove* target,const int s, const int n, const int direction);
	void Merge(PieceMove* source,PieceMove* target,int l,int m, int r);
	
	/***************TranspositionTable*****************/
	void EnterHashTable(EntryType entry_type,short eval,short depth,int TableNo);
	
	int LookUpHashTable(int alpha, int beta, int depth,int TableNo);
	void Hash_UnMakeMove(PieceMove* move,unsigned int nChessID, PieceIndex CurPosition[][9]);
	
	void Hash_MakeMove(PieceMove* move, PieceIndex CurPosition[][9]);
	void CalculateInitHashKey(PieceIndex CurPosition[][9]);
	void InitializeHashKey();
	
	/*Generate the Random 64-bit integer*/
	long long Rand64();
	/*Generate the Random 32-bit integer*/
	int Rand32();

private:
	int times;
	PieceMove m_best;

private:
	int m_HistoryTable[70][70];
	/*Buffer for sorting*/
	PieceMove m_TargetBuff[100];
	
	//For Hash-Table
	/*32-bit Hash-keys*/
	unsigned int m_nHashKey32[17][7][9];
	/*64-bit Hash-keys*/
	unsigned long long m_ulHashKey64[17][7][9];
	/*Point for the TranspositionTable*/
	HashItem *m_pTT[2];
	/*32-bit Hash-key*/
	unsigned int m_HashKey32;
	/*64-bit Hash-key*/
	unsigned long long m_HashKey64;
};

#endif	//_DSQTTHHENGINE_H